package baseclass.d_list;

import java.util.Random;

/**
 * 使用抛硬币来提高链表高度的  跳表算法
 *
 * @date 2020/3/14 11:16
 */
public class SkipList {

    private static final byte HEAD_NODE = -1;
    private static final byte DATA_NODE = 0;
    private static final byte TAIL_NODE = 1;
    /**
     * 最大高度是 log2^capacity + 1，这样能保证尽量二分
     */
    private final int MAX_LEVEL;
    private final int capacity;

    /**
     * Node节点，包含上下左右指针，数据，以及类型
     */
    static class Node {
        private Integer val;
        private Node up, down, left, right;
        private byte type;

        public Node(Integer val) {
            this(val, DATA_NODE);
        }

        public Node(Integer val, byte type) {
            this.val = val;
            this.type = type;
        }
    }

    private Node head;//每一层都有head和tail
    private Node tail;
    private int size;
    private int level;
    //随机算法，用来控制抛硬币。
    private Random random;

    public SkipList(int capacity) {
        this.head = new Node(null, HEAD_NODE);
        this.tail = new Node(null, TAIL_NODE);
        head.right = tail;
        tail.left = head;
        this.size = 0;
        this.level = 1;
        this.random = new Random(System.currentTimeMillis());
        this.capacity = capacity;
        //保证尽量二分,换底公式
        this.MAX_LEVEL = (int) (Math.log(capacity) / Math.log(2) + 1);
        System.out.println("capacity = " + capacity);
        System.out.println("MAX_LEVEL = " + MAX_LEVEL);
    }

    /**
     * 查找，从最顶层找到最底层.最核心的方法。每一层都向右向下
     *
     * @return 如果存在就返回对应的节点，不存在返回最近的前一个节点node，
     * 比如   1  4   5  6  6  6  8  12
     * 寻找6或7直接返回最后1个6，
     * 寻找9-11均返回8
     */
    private Node findItSelfOrNear(Integer val) {
        Node current = head;
        for (; ; ) {
            //如果当前节点值大于右侧节点，并且右侧节点不是尾巴节点，那么就往右移
            while (current.right.type != TAIL_NODE && val >= current.right.val) {
                current = current.right;
            }
            //否则val <  current.right.val 或者已经到了最后一部分,往下移动
            if (current.down != null) {
                current = current.down;
            } else {//已经是最后一层了
                break;
            }
        }
        //current.val <= val < current.right.val(if exist,perhaps is tail)
        return current;
    }

    public boolean contains(Integer element) {
        return findItSelfOrNear(element).val == element;
    }

    public void add(Integer val) {
        if (size >= capacity) throw new RuntimeException("full");
        Node pre = findItSelfOrNear(val);
        Node newNode = new Node(val);
        //1先把pre.right与newNode连接
        newNode.right = pre.right;
        pre.right.left = newNode;
        //2再把pre和last连接
        newNode.left = pre;
        pre.right = newNode;
        //是否需要把当前节点提上去
        addLevel(pre, newNode);
        size++;
    }

    public Integer delete(Integer val) {
        if (val == null) return null;
        Node node = findItSelfOrNear(val);
        //TODO  注意这里不能直接用 == ，因为是Integer对象，>= 128后用 == 判不是一个对象
        if (node.val - val == 0) {
            //删除node，并判断node是否有up，若有一直删除。
            // 注意如果该层只有head-node-tail,要删除整层
            doDelete(node);
            size--;
        }
        //else val is not exist,return null
        return null;
    }

    private void doDelete(Node node) {
        Node up;
        Node pre, next;
        do {
            up = node.up;
            //删除node本身即可，可以保证node.pre和node.next 肯定不是null。因为node不是head和tail
            pre = node.left;
            next = node.right;
            pre.right = next;
            next.left = pre;
            //help GC
            node.left = node.right = node.up = node.down = null;
            node = up;
        } while (up != null);
        //当前pre和next已经达到含有node节点的最高层，
        // 从含有node的最高层往下检测是否本层只有head和tail，是则删除(除了最后一层)
        //如果含有node层级删除node后没有其他节点，那么其父层级必然也无其他节点。
        //因为父层级节点 <= 当前层级节点。并且父层级至少1个有和当前层级一样的非node节点。
        //所以直接从最高层判断 即可

        while (level > 1 && head.right == tail) {
            //删除当前只有head和tail的层
            pre = head.down;//next head
            next = tail.down;//next tail
            //help GC
            head.left = head.right = head.up = head.down = null;
            tail.left = tail.right = tail.up = tail.down = null;
            head = pre;
            tail = next;
            //注意高度 -1
            level--;
        }

    }

    //TODO 跳表把当前节点提升的算法，该功能直接影响跳表的性能
    private void addLevel(Node pre, Node newNode) {
        //使用抛硬币来决定当前产生的高度，最大是MAX_HEIGHT
        int targetLevel = getRandomLevel();
        int nextLevel = 2;// 至少从第2层开始扩
//        while (random.nextDouble() < 0.5d) {
        while (nextLevel <= targetLevel) {
            //要扩建的层级已经大于level，那么需要再新建立一层
            if (nextLevel > level) {
                level++;
                //创建新的head和tail
                Node newHead = new Node(null, HEAD_NODE);
                Node newTail = new Node(null, TAIL_NODE);
                //新头连接，上下左右
                newHead.right = newTail;
                newHead.down = head;
                head.up = newHead;
                //新尾巴连接，上下左右
                newTail.left = newHead;
                newTail.down = tail;
                tail.up = newTail;
                //更新head和tail
                head = newHead;
                tail = newTail;
            }
            //当前节点newNode往前找，找到存在up节点的节点
            //已经保证当前层的head节点必定有up节点，
            // 因为在上面保证建立了一层，所以可以不用判pre != null
            //如果是刚刚新增了一层，那么pre会找到当前层的head，然后再up会到新的head
            while (pre != null && pre.up == null) {
                pre = pre.left;
            }
            //pre.up不为null，是提高的节点的pre
            pre = pre.up;
            //新建立newNode的上层节点
            Node upNode = new Node(newNode.val);
            upNode.down = newNode;
            newNode.up = upNode;
            //把upNode放在pre和pre.right之间
            upNode.right = pre.right;
            pre.right.left = upNode;
            upNode.left = pre;
            pre.right = upNode;
            //赋值，有可能需要再次提升~
            newNode = upNode;
            //更新当前层级
            nextLevel++;
        }
    }

    /**
     * 产生节点的高度。使用抛硬币。膜0高度一致自增
     */
    private int getRandomLevel() {
        int curLevel = 1;
        while ((random.nextInt() & 1) == 0)
            curLevel++;
        return Math.min(curLevel, MAX_LEVEL);
    }

    public void printSkipList() {
        System.out.println("size = " + size);
        Node temp = head;
        int curHeight = level;
        //遍历每一层
        while (temp != null) {
            System.out.printf("total level[%d]  current level [%d]", level, curHeight--);
            Node node = temp.right;
            while (node.type != TAIL_NODE) {
                System.out.print(" " + node.val + " ");
                node = node.right;
            }
            temp = temp.down;
            System.out.println();
        }
        System.out.println("===============");
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    public int size() {
        return this.size;
    }

    public static void main(String[] args) {
        int MAX_VAL = 64;
        SkipList skipList = new SkipList(MAX_VAL);
        for (int i = 1; i <= MAX_VAL; i++) {
            skipList.add(i);
        }
        skipList.printSkipList();
        System.out.println(skipList.contains(0));
        System.out.println(skipList.contains(20));
        /*Node right = skipList.head.right;
        skipList.delete(right.val);
        skipList.printSkipList();*/
        for (int i = MAX_VAL; i >= 2; i--) {
            skipList.delete(i);
            skipList.printSkipList();
        }
/*        skipList.delete(13);
        skipList.printSkipList();
        skipList.delete(15);
        skipList.printSkipList();*/

    }
}
